|
In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a ''map'', no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called ''adjacent'' if they share a common boundary that is not a corner, where corners are the points shared by three or more regions.〔From this paper: Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors.〕 For example, in the map of the United States of America, Utah and Arizona are adjacent, but Utah and New Mexico, which only share a point that also belongs to Arizona and Colorado, are not. Despite the motivation from coloring political maps of countries, the theorem is not of particular interest to mapmakers. According to an article by the math historian Kenneth May , “Maps utilizing only four colors are rare, and those that do usually require only three. Books on cartography and the history of mapmaking do not mention the four-color property.” Three colors are adequate for simpler maps, but an additional fourth color is required for some maps, such as a map in which one region is surrounded by an odd number of other regions that touch each other in a cycle. The five color theorem, which has a short elementary proof, states that five colors suffice to color a map and was proven in the late 19th century ; however, proving that four colors suffice turned out to be significantly harder. A number of false proofs and false counterexamples have appeared since the first statement of the four color theorem in 1852. The four color theorem was proven in 1976 by Kenneth Appel and Wolfgang Haken. It was the first major theorem to be proved using a computer. Appel and Haken's approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem. (If they did appear, you could make a smaller counter-example.) Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps. Showing this required hundreds of pages of hand analysis. Appel and Haken concluded that no smallest counterexamples exist because any must contain, yet do not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand . Since then the proof has gained wider acceptance, although doubts remain . To dispel remaining doubt about the Appel–Haken proof, a simpler proof using the same ideas and still relying on computers was published in 1997 by Robertson, Sanders, Seymour, and Thomas. Additionally in 2005, the theorem was proven by Georges Gonthier with general purpose theorem proving software. ==Precise formulation of the theorem== The intuitive statement of the four color theorem, i.e. 'that given any separation of a plane into contiguous regions, called a map, the regions can be colored using at most four colors so that no two adjacent regions have the same color', needs to be interpreted appropriately to be correct. First, all corners, points that belong to (technically, are in the closure of) three or more countries, must be ignored. In addition, bizarre maps (using regions of finite area but infinite perimeter) can require more than four colors. Second, for the purpose of the theorem, every "country" has to be a connected region, or contiguous. In the real world, this is not true (e.g. the Upper and Lower Peninsula of Michigan, Nakhchivan as part of Azerbaijan, and Kaliningrad as part of Russia are not contiguous). Because all the territory of a particular country must be the same color, four colors may not be sufficient. For instance, consider a simplified map: In this map, the two regions labeled ''A'' belong to the same country, and must be the same color. This map then requires five colors, since the two ''A'' regions together are contiguous with four other regions, each of which is contiguous with all the others. A similar construction also applies if a single color is used for all bodies of water, as is usual on real maps. For maps in which more than one country may have multiple disconnected regions, six or more colors might be required. A simpler statement of the theorem uses graph theory. The set of regions of a map can be represented more abstractly as an undirected graph that has a vertex for each region and an edge for every pair of regions that share a boundary segment. This graph is planar (it is important to note that we are talking about the graphs that have some limitations according to the map they are transformed from only): it can be drawn in the plane without crossings by placing each vertex at an arbitrarily chosen location within the region to which it corresponds, and by drawing the edges as curves that lead without crossing within each region from the vertex location to each shared boundary point of the region. Conversely any planar graph can be formed from a map in this way. In graph-theoretic terminology, the four-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color, or for short, "every planar graph is four-colorable" (; ). ==History== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Four color theorem」の詳細全文を読む スポンサード リンク
|